/**
 * 
 */
package com.gragra.sampling.nonproj.structures.nonprojective;
import java.util.BitSet;
import com.gragra.benchmark.FractionAblePopulationStructure;
import com.gragra.sampling.PopulationProbabilityAssigner;
import com.gragra.sampling.PopulationSamplingStructure;
import com.gragra.sampling.ThreadedUniformAccess;
import com.gragra.sampling.binary.ConvertSample;
import com.gragra.sampling.binary.HeadAssignmentStructure;
import com.gragra.sampling.binary.ThreadedToString;
import com.gragra.sampling.sequentialStructure.WordAndTagHolder;
/**
 * note that the root position is assumed to be the length of the original sentence, the head of the root is always the root
 * @author Christoph Teichmann
 * 17.08.2013
 */
public abstract class NonProjDepdTree extends WordAndTagHolder implements PopulationSamplingStructure, 
													ThreadedToString, FractionAblePopulationStructure, HeadAssignmentStructure
{
	/**
	 * 
	 * @return
	 */
	public int getNumberOfThreads()
	{return this.heads.length;}
	/**
	 * 
	 * @param wth
	 * @param threads
	 */
	public NonProjDepdTree(WordAndTagHolder wth, int threads, ConvertSample cs)
	{
		super(wth);
		int lengthPlusRoot = wth.getLength()+1;
		this.heads = new int[threads][lengthPlusRoot];
		this.daughters = new BitSet[threads][lengthPlusRoot];
		this.headLists = new BitSet[threads];
		for(int i=0;i<threads;++i)
		{
			this.headLists[i] = new BitSet();
			for(int j=0;j<lengthPlusRoot;++j)
			{
				this.daughters[i][j] = new BitSet();
				this.heads[i][j] = j == this.getRootPosition() ? this.getRootPosition() : -1;
			}
		}
		this.cs = cs;
	}
	/**
	 * returns true if the word is among the immediate descendants of the parent in question
	 * @param pos
	 * @param of
	 * @return
	 */
	public boolean isChild(int potentialChildPosition,int parentPosition,int inThread)
	{return this.heads[inThread][potentialChildPosition] == parentPosition;}
	/**
	 * returns the number of nodes attached directly below the given one identified by its position, also works for the root
	 * @param parentPosition
	 * @param thread
	 * @return
	 */
	public int numberOfChildren(int parentPosition,int thread)
	{return getDaughters(parentPosition,thread).cardinality();}
	/**
	 * returns the length of this sequence, if the parent is the root, returns the root for the root
	 * @param childPosition
	 * @param thread
	 * @return
	 */
	public int getParentPosition(int childPosition,int thread)
	{return this.heads[thread][childPosition];}
	/**
	 * returns -2 if the parent is root (since WordAndTagHolder uses -1 to indicate that no tag is present)
	 * @param childPosition
	 * @param thread
	 * @return
	 */
	public int getParentTag(int childPosition,int thread)
	{
		int parentPos = this.getParentPosition(childPosition, thread);
		if(parentPos == this.getRootPosition())
		{return -1;}
		else
		{return this.getTag(parentPos);}
	}
	/**
	 * returns -1 if the parent is root
	 * @param childPosition
	 * @param thread
	 * @return
	 */
	public int getParentWord(int childPosition,int thread)
	{
		int parentPos = this.getParentPosition(childPosition, thread);
		if(parentPos == this.getRootPosition())
		{return -1;}
		else
		{return this.getWord(parentPos);}
	}
	/**
	 *  method that should be used to attach words to a new head
	 * @param forPosition
	 * @param toHead
	 * @param inThread
	 * @throws IllegalArgumentException if the attachment would lead to a cycle
	 */
	public void setNewHead(int forPosition,int toHead,int inThread)
	{
		this.detach(forPosition, inThread);
		this.attach(forPosition, toHead, inThread);
		return;
	}
	/**
	 * may result in inconsistent state if called without calling detach before
	 * @param forPosition
	 * @param toHead
	 * @param inThread
	 * @param daught
	 */
	protected void attach(int forPosition, int toHead, int inThread)
	{
		this.getDaughters(toHead, inThread).set(forPosition);
		this.heads[inThread][forPosition] = toHead;
	}
	/**
	 * used to set the head of a position to some nonsensical value and manage the daughter values
	 * 
	 * calling this method leaves the structure in an inconsistent state, which can only be remedied by a subsequent call to
	 * attach, generally it is better to use the setNewHead method
	 * @param forPosition
	 * @param inThread
	 * @return the descendants of forPosition for programming efficiency reasons
	 */
	protected void detach(int forPosition, int inThread)
	{
		int oldHead = this.getParentPosition(forPosition, inThread);
		this.getDaughters(oldHead, inThread).clear(forPosition);
		this.heads[inThread][forPosition] = -1;
	}
	/**
	 * @param inThread
	 * @param oldHead
	 * @return
	 */
	public BitSet getDaughters(int pos,int inThread)
	{return this.daughters[inThread][pos];}
	/**
	 * 
	 */
	private final int[][] heads;
	/**
	 * 
	 */
	private final BitSet[][] daughters;
	/**
	 * 
	 */
	private final BitSet[] headLists;
	/**
	 * 
	 */
	private final ConvertSample cs;
	/**
	 * @return the cs
	 */
	public ConvertSample getConverter()
	{return this.cs;}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#getBest(com.gragra.sampling.PopulationProbabilityAssigner)
	 */
	@Override
	public String getBest(PopulationProbabilityAssigner pa)
	{return cs.getBest(this, pa);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#minRisk(com.gragra.sampling.PopulationProbabilityAssigner)
	 */
	@Override
	public String minRisk(PopulationProbabilityAssigner pa)
	{return cs.minRisk(this, pa);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#addSample()
	 */
	@Override
	public void addSample()
	{this.cs.addSample(this);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#setBest(int)
	 */
	@Override
	public void setBest(int num)
	{cs.setBest(this, num);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#initialize(com.gragra.sampling.PopulationProbabilityAssigner, com.gragra.sampling.ThreadedUniformAccess)
	 */
	@Override
	public void initialize(PopulationProbabilityAssigner pa,
			ThreadedUniformAccess tua)
	{
		for(int thread=0;thread<this.heads.length;++thread)
		{
			if(tua.nextBoolean(thread))
			{
				for(int i=0;i<this.getLength();++i)
				{
					BitSet bs = this.makeAllHeadCandidates(i, thread, pa);
					int choice = tua.nextInt(thread, 1, bs.cardinality());
					int head = -1;
					for(;choice>0;--choice)
					{head = bs.nextSetBit(head+1);}
					this.attach(i, head, thread);
				}
			}
			else
			{
				for(int i=this.getLength()-1;i>=0;--i)
				{
					BitSet bs = this.makeAllHeadCandidates(i, thread, pa);
					int choice = tua.nextInt(thread, 1, bs.cardinality());
					int head = -1;
					for(;choice>0;--choice)
					{head = bs.nextSetBit(head+1);}
					this.attach(i, head, thread);
				}
			}
		}
	}
	/**
	 * 
	 * @param thread
	 * @param rootChild
	 */
	@SuppressWarnings("unused")
	private void makeFlat(int thread, int rootChild)
	{
		//TODO
		for(int i=0;i<this.getLength();++i)
		{
			if(rootChild != i)
			{this.attach(i, rootChild, thread);}
		}
	}
	/**
	 * 
	 * @param pos
	 * @param thread
	 * @param npa
	 * @return
	 */
	protected BitSet makeAllHeadCandidates(int pos, int thread,
			PopulationProbabilityAssigner npa)
	{
		BitSet container = this.getPotentialHeadHolder(thread);
		container.set(pos);
		fillContainerWithChildren(pos, container, thread);
		container.flip(0, this.getRootPosition()+1);
		return container;
	}
	/**
	 * @param pos
	 * @param thread
	 * @param container
	 */
	protected void fillContainerWithChildren(int forPos, BitSet container, int thread)
	{
		BitSet children = this.getDaughters(forPos, thread);
		for(int child=children.nextSetBit(0);child>=0;child = children.nextSetBit(child+1))
		{
			container.set(child);
			addRecursively(child,container,thread);
		}
	}
	/**
	 * 
	 * @param child
	 * @param container
	 * @param thread
	 */
	private void addRecursively(int head, BitSet container, int thread)
	{
		BitSet children = this.getDaughters(head, thread);
		for(int child=children.nextSetBit(0);child>=0;child = children.nextSetBit(child+1))
		{
			container.set(child);
			addRecursively(child,container,thread);
		}
	}
	/**
	 * 
	 * @param position
	 * @param inThread
	 * @return
	 */
	protected boolean isDetached(int position,int inThread)
	{return this.getParentPosition(position, inThread) == -1;}
	/**
	 * 
	 * @param npa
	 * @param tua
	 * @return 
	 */
	protected int attachOneToRoot(PopulationProbabilityAssigner npa,int thread, ThreadedUniformAccess tua)
	{
		int h = tua.nextInt(thread,0,this.getLength()-1);
		this.attach(h, this.getRootPosition(), thread);
		return h;
	}
	/**
	 * 
	 * @return
	 */
	public int getRootPosition()
	{return this.getLength();}
	/**
	 * 
	 * @return
	 */
	private BitSet getPotentialHeadHolder(int forThread)
	{
		this.headLists[forThread].clear();
		return headLists[forThread];
	}
	@Override
	public int getHeadPosition(int forWord, int thread)
	{return this.getParentPosition(forWord, thread);}
	@Override
	public double getNumberSeen(String gold)
	{return cs.getNumberSeen(gold);}
	@Override
	public String toString(int thread)
	{
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<this.getLength();++i)
		{
			if(i!=0)
			{sb.append(" ");}
			sb.append(this.getParentPosition(i, thread));
		}
		return sb.toString();
	}
	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString()
	{
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<this.getNumberOfThreads();++i)
		{
			if(i!=0)
			{sb.append("\r\n");}
			sb.append(this.toString(i));
		}
		return sb.toString();
	}
	/**
	 * 
	 * @return
	 */
	public int getDependencyRootPosition()
	{return this.getRootPosition();}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.PopulationSamplingStructure#resample(com.gragra.sampling.PopulationProbabilityAssigner, double, int, com.gragra.sampling.ThreadedUniformAccess)
	 */
	@Override
	public void resample(PopulationProbabilityAssigner pa, double annealing,
			int thread, ThreadedUniformAccess tua)
	{
		if(this.getLength()==1)
		{return;}
		resampleRoot(pa,annealing,thread,tua);
		for(int pos=0;pos<this.getLength();++pos)
		{
			if(this.skip(pos,pa,thread))
			{continue;}
			resampleAtPosition(pos,pa,annealing,thread,tua);
		}
	}
	/**
	 * 
	 * @param pa
	 * @param annealing
	 * @param thread
	 * @param tua
	 */
	protected abstract void resampleRoot(PopulationProbabilityAssigner pa,
			double annealing, int thread, ThreadedUniformAccess tua);
	/**
	 * 
	 * @param pos
	 * @param pa
	 * @param thread
	 * @return
	 */
	protected boolean skip(int pos, PopulationProbabilityAssigner pa, int thread)
	{return false;}
	/**
	 * 
	 * @param pos
	 * @param candidates
	 * @param pa
	 * @param annealing
	 * @param thread
	 * @param tua
	 */
	protected abstract void resampleAtPosition(int pos,	PopulationProbabilityAssigner pa, double annealing, int thread,
			ThreadedUniformAccess tua);
	/**
	 * 
	 * @param pa
	 * @param annealing
	 * @return
	 */
	protected double makeLogProbForThisConsideringAnnealing(PopulationProbabilityAssigner pa, double annealing, int thread)
	{return pa.makeLogProb(this, thread)*annealing;}
}